package com.demo.jzoffer2;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author gy
 * @date 2022/11/6
 */
public class Test1106_2 {

    /**
     * 给你一个整数数组 nums 和一个整数 k 。
     * <p>
     * 每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。
     * <p>
     * 返回你可以对数组执行的最大操作数。
     * <p>
     * 输入：nums = [1,2,3,4], k = 5
     * 输出：2
     * 解释：开始时 nums = [1,2,3,4]：
     * - 移出 1 和 4 ，之后 nums = [2,3]
     * - 移出 2 和 3 ，之后 nums = []
     * 不再有和为 5 的数对，因此最多执行 2 次操作。
     *
     * @param nums
     * @param k
     * @return
     */
    public int maxOperations(int[] nums, int k) {
        // 思路分析：拿数组的 第一个数 和 其他数相加  与 k 比较
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            // 第一个元素
            int firstNum = nums[0];
            // 相加 等于 k 的另一个元素
            int nextNum = k - firstNum;
            // 拿 数组的其余元素 和 nextNum 作比较
            // 若相同则去除这两个元素，同时 max + 1
            for (int j = 1; j < nums.length; j++) {
                if (nums[j] == nextNum) {
                    // 移除选定的元素  把最后一个元素替代 选定的元素
                    nums[j] = nums[nums.length - 1];
                    nums = Arrays.copyOf(nums, nums.length - 1);
                    // 移除第一个元素
                    nums[i] = nums[nums.length - 1];
                    nums = Arrays.copyOf(nums, nums.length - 1);
                    max++;
                    break;
                }
            }
        }
        return max;
    }


    public int maxOperations2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        //统计每个数据出现的次数，key为数据，value为次数
        for (int num : nums) {
            Integer i = map.getOrDefault(num, 0);
            map.put(num, i + 1);
        }
        int result = 0;
        for (int num : nums) {
            // 求和达到K的数据
            int x = k - num;
            // 从map获取x
            int i = map.get(num);
            //如果次数小于等于0，说明数据被使用过了【就算后面遍历到他，也可以跳过了】
            if (i <= 0) {
                continue;
            }
            //统计数量减一，先减去，防止两个相同的数据相加达到K，而只有一个数据
            //【有个大兄弟有疑问，为什么直接删了。补充一下：因为是两遍循环，第一次就统计过所有的数据了，如果后面的if无法进入，那么之后也不可能了，删了就删了，无所谓了。】
            map.put(num, i - 1);
            // 是否有 另一个数据。且统计的数量大于0
            if (map.containsKey(x) && map.get(x) > 0) {
                result++;//结果+1
                map.put(x, map.get(x) - 1);// 数量减一
            }
        }
        return result;
    }

    /**
     * 思路分析
     * 1、先对数组进行排序
     * 2、双指针 i=0 j= nums.length-1
     * 判断 nums[i] + nums[j] == k
     * 如果 比 k 小 说明：左边的数小了，左指针右移动
     * 如果 比 k 大 说明：右边的数大了，右指针左移动
     * 直到 左右指针相遇时，所有的元素遍历结束
     * @param nums
     * @param k
     * @return
     */
    public int maxOperations3(int[] nums, int k) {
        Arrays.sort(nums);
        int i = 0 ,j= nums.length-1;
        int result = 0;
        while (i<j) {
            int sum = nums[i] + nums[j];
            if (sum == k){
                result++;
                i++;
                j--;
            }else if (sum < k){
                i++;
            }else {
                j--;
            }
        }
        return result;
    }


    @Test
    public void test1() {
        int[] nums = {1, 2, 3, 4,2};
        int k = 5;
        maxOperations3(nums, 5);
    }


    /**
     * 输入：nums = [3,1,3,4,3], k = 6
     * 输出：1
     * 解释：开始时 nums = [3,1,3,4,3]：
     * - 移出前两个 3 ，之后nums = [1,4,3]
     * 不再有和为 6 的数对，因此最多执行 1 次操作。
     */
    @Test
    public void test2() {

    }


}
